Binary search

This is one of the simplest ways of searching through large amounts of data. It assumes that the data has some kind of key that can be used to say whether or not you have found it and that the data is stored in order.

In essence:

• Chop the data in half.
• If the key you’re looking for is greater than the one at the halfway point
• Chop the data for the smaller valued keys in half and check again
• Otherwise chop the data for the larger valued keys
• If one of the keys matches you found what you’re looking for
• Keep doing this until you’ve found the key you’re looking for or neither half of the remaining data matches the keys you have.

The actual algorithm has some checks around end conditions and bit this is the essence. Divide and conquer until you find what you’re looking for or it isn’t there.

There are a number of data structures like B-trees that let you take an arbitrary list of keys and create a binary searchable list that has pointers to the data you want with a minimum of effort.

Once you’ve scanned some data and created a B-tree with key values and where to find the data you have created an index that will allow you to quickly get to keyed data. There are many data structures that can be used for things like searching strings, or attributes of images. The principle is the same: work your way down a data structure looking for the key (or set of keys for the more sophisticated structures) until you either get a link to where the data is or the search fails.